/*
大家好，这是我之前面试时遇到的一个问题，
当时没有解决，后来思考了几天也没有结果，
特拿出来请大家指点迷津。

题目是这样的：
20个排成一排的硬币，
每个硬币初始的朝向是随机的。
问20个硬币中连续5个以上（含5个）正面朝上的概率是多少？
要求同时给出程序解法和数学推理。

程序解法我是这样写的：
用一个32位整数的低20位表示这一排硬币，
那么这20个硬币的所有可能排列就是从0x00000到0xFFFFF的所有整数。
我只要检查这些整数中至少包含连续5个1的整数即可，
最后把至少包含连续5个1的整数个数除以总的整数个数2^20即为其概率。
我计算得到的结果是0.249870300293。
顺便说一句，当将硬币的个数从5逐个增加到20，得到的概率也是逐渐增加的，
中间似乎隐藏着某种递增关系，
分析这个递增关系也许会对推导数学结论有一定的帮助。
以下是我用python写的代码，
因为只是proof-of-concept，
也没有考虑风格之类的问题，
大家将就看了。
我现在的问题是，
如何从数学推理得出同样的结果呢。
*/
#include "junix.h"
using namespace std;

//naive solution
int naive(int m=20,int n=5) {
	unsigned max = 0xFFFFF;
	unsigned tag = 0x1F;
	unsigned x, y;
	bool match = false;
	unsigned count = 0; 

	for (unsigned i=0;i<=max;i++) {
		match = false;
		for (int j=0;j<16;j++) {
			x = (i>>j)&tag;
			if ((y=(x^tag))==0) {
				match=true;
				break;
			}
		}

		if (match)
			++ count;
	}

	return count;
}

//junix's solution
uint64_t Cmn(uint64_t m,uint64_t n) {
	uint64_t p=1,q=1;
	for (uint64_t i=0;i<n;i++) {
		p *= (m-i);
		q *= (i+1);
	}

	return p/q;
}

uint64_t fix_F(uint64_t n,uint64_t m) {
	if (m==n) return 1;

	uint64_t t  = (m-n)/(n+1);
	if ((m-n)%(n+1)!=0) ++t;
	t = (m-t)/n;
	std::cout<<t<<" ";

	uint64_t total = 0;
	for (uint64_t i=1;i<=t;i++)
		total += Cmn(m-i*n+1,i);

	//std::cout<<total<<" ";
	return total;
}

uint64_t F(uint64_t n,uint64_t m) {
	assert(m>=n);
	uint64_t total = 0;
	for (uint64_t i=n;i<=m;i++) {
		total += fix_F(i,m);
	}

	return total;
}

int main(int argc, char **argv)
{
	/*
	double d = pow(2.0,20.0);
	std::cout<<static_cast<double>(naive())/d<<std::endl;;
	*/

	std::cout<<naive()<<std::endl;
	std::cout<<F(5,20)<<std::endl;
}
